#include <iostream>
#include "DynamicArray.h"
#include <cmath>
namespace DARRAY
{


DynamicArray::DynamicArray():size(0),capacity(15)
{
    array = new ElementType [capacity];
    Free = nullptr;
    Compare = nullptr;
    Print = nullptr;
}

DynamicArray::DynamicArray(const DynamicArray& a)
{
    size = a.size;
    capacity = a.capacity;
    array = new ElementType [capacity];
    for(size_t i = 0; i < size; i++)
    {
        array[i] = a.array[i];
    }
    Free = a.Free;
    Compare = a.Compare;
    Print = a.Print;
}

DynamicArray& DynamicArray::operator=(const DynamicArray& a)
{
    if(this != &a)
    {
        delete []array;
        size = a.size;
        capacity = a.capacity;
        array = new ElementType[capacity];
        for(int i = 0; i < size; i++)
        {
            array[i] = a.array[i];
        }
    }
    return *this;
}

void DynamicArray::InsertTail(const ElementType &element)  //不扩容: O(1)  扩容:O(n)
{
    if(size == capacity)  //数组满
    {
        ReSize(capacity * 2);
    }
    array[size++] = element;
}

void DynamicArray::InsertHead(const ElementType &element)
{
    if(size == capacity)  //数组满
    {
        ReSize(capacity * 2);
    }
    for(size_t i = size; i > 0; i--)
    {
        array[i] = array[i - 1];
    }
    array[0] = element;
    size++;
}

void DynamicArray::InsertByIndex(const ElementType &element, size_t index)
{
    if(index > size)
    {
        std::cout<<"插入位置非法!\n";
        return ;
    }
    if(size == capacity)  //数组满
    {
        ReSize(capacity * 2);
    }
    for(size_t i = size; i > index; i--)
    {
        array[i] = array[i - 1];
    }
    array[index] = element;
    size++;
}

void DynamicArray::RemoveByIndex(size_t index)  //O(n)
{
    if(index >= size)
    {
        std::cout<<"删除位置不合法!\n";
        return ;
    }

    for(size_t i = index; i < size - 1; i++)
    {
        array[i] = array[i + 1];
    }
    size--;
}

void DynamicArray::RemoveByElement(const ElementType& element)  //O(n^2)
{
    for(size_t i = 0; i < size; i++)
    {
        if(array[i] == element)
        {
            RemoveByIndex(i);
            i--;
        }
    }
}

ElementType* DynamicArray::FindByIndex(size_t index)  //O(1)
{
    if(index >= size)
    {
        std::cout<<"位置非法!\n";
        return nullptr;
    }
    return &array[index];
}

DynamicArray DynamicArray::FindByElement(const ElementType &element)  //O(n)
{
    DynamicArray result;
    for(size_t i = 0; i < size; i++)
    {
        if(array[i] == element)
        {
            result.InsertTail(array[i]);
        }
    }
    return result;
}

void DynamicArray::UpdateByIndex(size_t index, const ElementType &newValue)  //O(1)
{
    if(index >= size)
    {
        std::cout<<"修改位置不合法!\n";
        return ;
    }
    array[index] = newValue;
}

void DynamicArray::UpdateByElement(const ElementType &oldValue, const ElementType &newValue)  //O(n)
{
    for(size_t i = 0; i < size; i++)
    {
        if(array[i] == oldValue)
        {
            array[i] = newValue;
        }
    }
}

ElementType &DynamicArray::operator[](int index)
{
    return array[index];
}

void DynamicArray::Sort()
{
    FastSort(0,size - 1,0,2 * log2(size));   
}

void DynamicArray::Duplicate()  //O(n)
{
    for(size_t i = 1; i < size; i++)
    {
        if(array[i] == array[i - 1])
        {
            RemoveByIndex(i);
            i--;
        }   
    }
}

DynamicArray DynamicArray::Merge(const DynamicArray &a)  //O(n)
{
    DynamicArray result;
    size_t first = 0;  //当前数组
    size_t second = 0;  //传进来的数组

    while(first < this->size && second < a.size)
    {
        if(Compare(array[first] , a.array[second]) <= 0)
            result.InsertTail(array[first++]);
        else
            result.InsertTail(a.array[second++]);
    }

    while(first < this->size)
        result.InsertTail(array[first++]);
    while(second < a.size)
        result.InsertTail(a.array[second++]);

    return result;
}

DynamicArray DynamicArray::FindInterSection(const DynamicArray &a)
{
    DynamicArray result;
    size_t first = 0;  //当前数组
    size_t second = 0;  //传进来的数组
    while(first < this->size && second < a.size)
    {
        if(array[first] == a.array[second])
        {
            result.InsertTail(array[first++]);
            second++;
        }
        else if(Compare(array[first] , a.array[second]) < 0)
        {
            first++;
        }
        else if(Compare(array[first] , a.array[second]) > 0)
        {
            second++;
        }
    }
    
    return result;
}

DynamicArray DynamicArray::FindUnionSection(const DynamicArray &a)  //O(n)
{
    DynamicArray result;
    size_t first = 0;  //当前数组
    size_t second = 0;  //传进来的数组
    while(first < this->size && second < a.size)
    {
        if(array[first] == a.array[second])
        {
            result.InsertTail(array[first++]);
            second++;
        }
        else if(Compare(array[first] , a.array[second]) < 0)
        {
            result.InsertTail(array[first++]);
        }
        else if(Compare(array[first] , a.array[second]) > 0)
        {
            result.InsertTail(a.array[second++]);
        }
    }
    while(first < this->size)
        result.InsertTail(array[first++]);
    while(second < a.size)
        result.InsertTail(a.array[second++]);
    return result;
}

DynamicArray DynamicArray::FindDifference(const DynamicArray &a)
{
    DynamicArray result;
    size_t first = 0;  //当前数组
    size_t second = 0;  //传进来的数组
    while(first < this->size && second < a.size)
    {
        if(array[first] == a.array[second])
        {
            second++;
            first++;
        }
        else if(Compare(array[first] , a.array[second]) < 0)
        {
            result.InsertTail(array[first++]);
        }
        else if(Compare(array[first] , a.array[second]) > 0)
        {
            result.InsertTail(a.array[second++]);
        }
    }
    while(first < this->size)
        result.InsertTail(array[first++]);
    while(second < a.size)
        result.InsertTail(a.array[second++]);
    return result;
}

bool DynamicArray::operator==(const DynamicArray &a)  //O(n)
{
    if(this->size != a.size)
        return false;
    size_t first = 0;  //当前数组
    size_t second = 0;  //传进来的数组
    // while(first < this->size && second < a.size)
    // {
    //     if(array[first++] != a.array[second++])
    //         return false;
    // }
    for(size_t i = 0; i < this->size; i++)
    {
        if(Compare(array[i] , a.array[i]) != 0)
            return false;
    }
    return true;
}

size_t DynamicArray::BinarySearch(const ElementType &element)
{
    size_t left = 0;
    size_t right = size - 1;
    while(left <= right)
    {
        size_t mid = left + (right - left) / 2;
        if(array[mid] == element)
        {
            return mid;
        }
        else if(Compare(array[mid] , element) > 0)
        {
            if(mid == 0)
                return ULONG_MAX;
            right = mid - 1;
        }
        else
        {
            left = mid + 1;
        }
    }
    return ULONG_MAX;
}

bool DynamicArray::Contains(const DynamicArray &a)
{
    // DynamicArray s = FindInterSection(a);  //O(2n)
    // return s == a;

    size_t j = 0;
    for(size_t i = 0; i < size; i++)  //O(n)
    {
        if(array[i] == a.array[j])
            j++;
    }
    return j == a.size;
}

bool DynamicArray::ContinueContains(const DynamicArray &a)  //滑动窗口
{
    for(int i = 0; i <= size - a.size; i++)
    {
        DynamicArray tmp = SubSquence(i, a.size);
        tmp.Compare = this->Compare;
        if (tmp == a)
            return true;
    }
    return false;
}

DynamicArray DynamicArray::SubSquence(size_t index, size_t len)
{
    DynamicArray result;
    if(index + len > size)
        return result;
    
    for(size_t i = 0; i < len; i++)
    {
        result.InsertTail(array[index + i]);
    }
    return result;
}

size_t DynamicArray::partition(size_t start, size_t end)
{
    size_t left = start;
    size_t right = end;
    ElementType temp = array[start];
    while(left < right)
    {
        //从右往左找比基准值小的值
        while(array[right] > temp && left < right)
        //while(a[right] < temp && left < right)
            right--;
        if(left < right)
            array[left++] = array[right];  //把比基准值小的数放到左边


        //从左往右找比基准值大的值
        while(array[left] < temp && left < right)
        //while(a[left] > temp && left < right)
            left++;
        if(left < right)
            array[right--] = array[left];  //把比基准值大的数放到右边
    }
    array[left] = temp;
    return left;
}

void DynamicArray::FastSort(size_t start, size_t end,size_t CurDepth,size_t MaxDepth)
{
    if(start >= end)
    {
        return;
    }

    //如果没有达到最大的递归深度
    if(CurDepth < MaxDepth)
    {
        size_t par = partition(start,end);  //对数列分组
        if(par != 0)
            FastSort(start,par - 1,CurDepth + 1,MaxDepth);
        FastSort(par + 1,end,CurDepth + 1,MaxDepth);
    }
    //超过最大深度，该用插入排序/选择排序
    else
    {
        std::cout<<"插入排序"<<std::endl;
        InsertSort(start,end);
    }
}

void DynamicArray::InsertSort(size_t start, size_t end)
{
    for(size_t i = start + 1; i <= end; i++)
    {
        size_t j = i;
        ElementType temp = array[i];
        for(; j > start; j--)
        {
            if(array[j - 1] > temp)
            {
                array[j] = array[j - 1];
            }
            else
                break;
        }
        array[j] = temp;
    }
}

void DynamicArray::ReSize(size_t capacity)
{
    this->capacity = capacity;
    this->size = size > capacity ? capacity : size;
    ElementType *newPtr = new ElementType[capacity];
    for(size_t i = 0; i < size; i++)
    {
        newPtr[i] = array[i];
    }
    delete []array;
    array = newPtr;
}

DynamicArray::~DynamicArray()
{
    if(Free)
    {
        for(size_t i = 0; i < size; i++)
        {
            Free(array[i]);
        }
    }
    if(array != nullptr)
        delete []array;
}

void DynamicArray::SetFreeFunc(void (*Free)(ElementType ))
{
    this->Free = Free;
}

void DynamicArray::SetCompareFunc(int (*Compare)(ElementType,ElementType))
{
    this->Compare = Compare;
}

void DynamicArray::SetPrintFunc(void (*Print)(ElementType))
{
    this->Print = Print;
}

void DynamicArray::show()
{
    for(size_t i = 0; i < size; i++)
    {
        if(Print)
            Print(array[i]);
        else
            std::cout<<array[i]<<" ";
    }
    //std::cout<<std::endl;
}
}